import java.util.*;

class Student {
    public String id;
    public Student(String id) {
        this.id = id;
    }

    /**
     * 使可比较
     * @param o
     * @return
     */
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return Objects.equals(id, student.id);
    }

    /**
     * 拿到哈希值
     * @return
     */
    @Override
    public int hashCode() {
        return Objects.hash(id);
    }

    /**
     * 打印Student
     * @return
     */
    @Override
    public String toString() {
        return "Student{" +
                "id='" + id + '\'' +
                '}';
    }
}
public class Test {
    /**
     * 宝石和石头
     * @param jewels
     * @param stones
     * @return
     */
    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> set = new TreeSet<>();
        for(int i = 0;i < jewels.length();i++) {
            char ch = jewels.charAt(i);
            set.add(ch);
        }

        int count = 0;
        for(int i = 0;i < stones.length();i++) {
            char ch = stones.charAt(i);
            if(set.contains(ch)) {
                count++;
            }
        }
        return count;
    }
    /**
     * 只出现一次的数字
     * @param nums
     * @return
     */
    public int singleNumber(int[] nums) {
        TreeSet<Integer> set = new TreeSet<>();
        for(int i = 0;i < nums.length;i++) {
            if(set.contains(nums[i])) {
                set.remove(nums[i]);
            }else {
                set.add(nums[i]);
            }
        }

        for(int i = 0;i < nums.length;i++) {
            if(set.contains(nums[i])) {
                return nums[i];
            }
        }

        return -1;
    }
    /**
     * Map Set
     * @param args
     *      2.搜索
     *      3.Map的使用
     *      4.Set的说明
     *      5.哈希表
     */
    /**
     * 哈希表
     *      1.概念
     *      2.冲突-概念
     *      3.冲突-避免
     *      4.冲突-避免-哈希函数设计
     *      5.冲突-避免-负载因子调节
     *      6.冲突-解决
     *      7.冲突-解决-闭散列
     *      8.冲突-解决-开散列
     *      9.冲突严重时的解决办法
     *      10.实现
     *      11.性能分析
     *      12.和java类集的关系
     */
    public static void main19(String[] args) {
        Student student = new Student("123456");
        Student student2 = new Student("123456");
        HashBuck2<Student,Integer> hashBuck2 = new HashBuck2<>();
        hashBuck2.push(student,888);
        System.out.println(hashBuck2.get(student2));

    }
    public static void main18(String[] args) {
        HashBuck hashBuck = new HashBuck();
        hashBuck.push(1,888);
        hashBuck.push(2,888);
        hashBuck.push(3,888);
        hashBuck.push(4,888);
        hashBuck.push(5,888);
        hashBuck.push(6,888);
        hashBuck.push(14,999);
        hashBuck.push(7,888);
        System.out.println();
        System.out.println(hashBuck.get(14));
        System.out.println(hashBuck.get(100));
    }
    public static void main17(String[] args) {
        /**
         *  和java类集的关系
         * @param args
         *      1.HashMap HashSet是java使用哈希表实现的Map和Set的子类
         *      2.java解决hash冲突的方法是哈希桶
         *      3.java桶超过阀值时,将链表转化为红黑树
         *      4.java计算哈希值,是调用类的hashCode方法,
         *      进行key的相等比较是通过Key的equals方法,
         *      所以如果要用自定义类的HashMap/HashSet的key值,必须重写这两个方法
         */
    }

    public static void main16(String[] args) {
        /**
         * 性能分析
         *      哈希表增删查时间复杂度为O(1)
         */
    }
    public static void main15(String[] args) {
        /**
         *  冲突严重时的解决办法,进行继续转化
         *       1.每个桶背后是另一个哈希表
         *       2.每个桶背后是一颗搜索树1
         */
    }
    public static void main14(String[] args) {
        /**
         * 冲突-解决-开散列/哈希桶
         *      开散列/链地址法/开链法,是数组 + 链表的组成
         *      当出现冲突时,在相同地址处通过尾插放在该元素后面,每一个单链表又被称为桶
         */
    }
    public static void main13(String[] args) {
        /**
         * 冲突-解决-闭散列/开放地址法
         *      当发生哈希冲突时,如果哈希表未被装满说明散列表必然还有空位置,
         *      那么可以把key存放到冲突位置的下一个空位置
         *
         *      寻找空位置
         *      1.线性探测
         *          依次往后进行寻找,空位置就插入
         *      2.二次探测
         *          通过方法:Hi= (H0 + i^2) % m 或Hi= (H0 - i^2) % m
         *          找到空位置插入
         */
    }
    public static void main12(String[] args) {
        /**
         * 冲突-解决
         *      常用解决方法:闭散列 开散列
         */
    }
    public static void main11(String[] args) {
        /**
         * 冲突-避免-负载因子调节
         *      负载因子 = 存入表的个数 / 散列表的长度
         *      一般java负载因子 <= 0.75,当超过时,反向修改散列表的长度
         */
    }
    public static void main10(String[] args) {
        /**
         * 冲突-避免-哈希函数设计
         *      哈希函数设计原则:
         *          1.哈希函数的定义域必须包括需要存储的全部关键码,
         *          而如果散列允许有m个地址时,其值域必须在0-m-1之间
         *          2.哈希函数计算的地址能均匀分布整个空间
         *          3.哈希函数应该比较简单
         *      常见哈希函数
         *          1.直接定制法
         *              取关键字的某个线性函数作为散列地址:Hash(Key) = A*Key + B
         *              优点:简单 均匀 缺点:必须要事先知道关键字的分布情况  使用场景:适合查找比较小且连续的情况
         *          2.除留余数法
         *              设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，
         *              按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址
         */
    }
    public static void main9(String[] args) {
        /**
         * 冲突-避免
         * 冲突是必然的,我们要做的就是降低冲突率
         */
    }
    public static void main8(String[] args) {
        /**
         * 冲突-概念
         *  不同关键字通过相同哈希方法,得到相同哈希地址,该现象称为哈希碰撞/冲突
         */
    }
    public static void main7(String[] args) {
        /**
         * 概念:不经过任何比较,一次直接从表中搜索得到要搜索的元素.
         * 如果构造一种存储结构通过一个函数(hashFunc)使存储位置与它的关键码之间
         * 能够建立一一映射的关系,那么在查找时就能通过该函数很快找到该元素.
         * 该方式为哈希/散列方法,而这种结构称为哈希表/散列表
         */
    }
    /**
     * Set的说明
     *   Map和Set的区别,Map不继承于Collection,Set继承于Collection
     *   Set只存储Key
     */
    public static void main6(String[] args) {
        /**
         * Set常用方法说明
         *      1.Set继承于Collection
         *      2.Set只存储Key,并且要求Key唯一
         *      3.TreeSet底层就是使用Map实现的(TreeMap),其Key与Object类的默认值插入到Map中的
         *      4.Set最大的功能是对元素进行去重
         *      5.实现Set的常用接口有TreeSet HashSet LinkedSet,LinkedSet是双链表在HashSet基础上维护双向链表来记录次序
         *      6.Set中Key不能修改,如果要修改,必须删除,重新add
         *      7.TreeSet,Key不能为null,HashSet可以
         *      8.TreeSet HashSet区别
         */
    }
    /**
     * Map的使用
     *      1.关于Map的说明
     *      2.Map.Entry<K,V>的说明
     *      3.Map的常用方法说明
     */
    public static void main5(String[] args) {
        /**
         * Map的常用方法说明
         *      1.Map是一个接口,不能直接进行实例化,如果要实例化只能实例化实现了该接口的TreeMap/HashMap类
         *      2.key的键值是唯一的,value的键值可以重复
         *      3.在TreeMap进行插入键值对时,key不能为空,为空将会报NullException异常,value可以为空,HashMap的key,value都可以为空
         *      4.Map中的key可以全部提取出来,存储到Set中进行访问(因为Key不能重复)
         *      5.Map中的Value可以全部提取出来,存储到Collection中进行访问(value可能有重复)
         *      6.Map中的键值不能直接修改,必须要删除后进行修改,value可以直接修改
         *      7.HashMap和TreeMap的区别
         */
        Map<String,Integer> map = new TreeMap<>();
        //put(Key,Value)->设置key对应的value
        map.put("qinBo",3);
        map.put("is",4);
        map.put("da Shuai Bi",5);
        //V get(Key)->返回Key对应的Value,如果不存在默认返回null
        Integer ret = map.get("qinBo");
        System.out.println(ret);
        Integer ret2 = map.get("qinBoIsDaShuaiBi");
        System.out.println(ret2);//null
        //V getOrDefault(key,defaultValue)->如上,不过可以设定默认值
        Integer ret3 = map.getOrDefault("qinbois",9);
        System.out.println(ret3);
        //V remove(key)删除Key对应的映射关系,返回设定的Value值
        Integer ret4 = map.remove("is");
        System.out.println(ret4);
        //Set<Key> keySet(),返回key的集合(不可重复)
        Set<String> ret5 = map.keySet();
        System.out.println("ret5: " + ret5);
        //Collection<Value> values(),返回Value的集合(可重复)
        Collection<Integer> ret6 = map.values();
        System.out.println(ret6);
        //Set<Map.Entry<K,V>> entrySet(),返回所有Key-Value映射关系
        Set<Map.Entry<String,Integer>> ret7 = map.entrySet();
        for(Map.Entry<String,Integer> x:ret7) {
            System.out.println("Key: " + x.getKey() + " Value: " + x.getValue());
        }
        //boolean containsKey(Object key)->判断是否存在key
        //boolean containsKey(Object value)->判断是否存在value
    }
    public static void main4(String[] args) {
        /**
         * 关于Map.Entry<K,V>的说明->可以理解为节点
         *     是Map内部实现的用来存放<K,V>键值对应关系的映射
         *     内部提供了K(getKey()),V(getValue())的获取,Value的设置(setValue)以及Key的比较方式
         */

    }
    public static void main3(String[] args) {
        /**
         * 关于Map的说明
         *      Map是一个接口类,不继承于Collection,
         *      该类中存储的是<K,V>的键值,且K是唯一的不可重复
         */
    }
    /**
     * 搜索
     * @param args
     *      1.概念及场景
     *      2.模型
     */
    public static void main2(String[] args) {
        /**
         * 模型
         *      Set-Key(模型),查找是否存在
         *      Map-Key-Value(模型),查找Key对应的Value,或Value对应的Key
         */
    }
    public static void main1(String[] args) {
        /**
         * 概念及场景
         *      Map和Set是专门进行搜索的容器或数据结构,
         *      其搜索的效率与其具体的实例化子类有关
         */
    }
}
